package com.atguigu.sort;

import java.util.Arrays;

/**
 * 快速排序
 * 是对冒泡的一种优化
 *
 * 快速排序的特点如下:
 * 1. 普通冒泡是相邻位置冒泡, 快速排序则是从左右两侧向内递进, 根据中值进行冒泡
 * 2. 一轮排序, 中值一旦确定, 就不再变化, 但中值所在位置可能会变化.
 * 2.1 在中值唯一的情况下, 一轮排序到最后, 一定能保证左侧数均小于中值, 右侧数均大于中值
 * 2.2 在中值不唯一的情况下, 一轮排序到最后, 一定能保证左侧数均小于中值, 右侧数均大于等于中值
 *
 * 耗时:
 * work: 0.02s
 * 千万: 1s (波动较大)
 * 亿级: 4.2s (波动较大)
 */
public class QuickSort {

    public static void main(String[] args) {
//        int[] arr={1,-2,0,5,9,-10,5};
//        int[] arr={1,-2,5,0,9,-10,-3,0};
        int[] arr=ArrCreator.createRandArr(ArrCreator.testVelocitySize*100);
        ArrCreator.beforeSort();
        sort(arr,0,arr.length-1);
        ArrCreator.afterSort();
//        System.out.println("arr="+Arrays.toString(arr));
    }

    public static void sort(int[] arr,int leftIndex,int rightIndex){
        // 搜寻左索引
        int searchLeftIndex=leftIndex;
        // 搜寻右索引
        int searchRightIndex=rightIndex;
        // 中间值. 本方法的一次调用目标, 是将所有比中间值小的数, 全部放在中间值左侧; 比中间值大的数, 全部放在中间值右侧
        // 这种情况, 可能出现中间值自身索引也变动的情况, 所以中间值索引可能是会变动的
        int middleVal=arr[(leftIndex+rightIndex)/2];
        int temp;

        // 左右边界逐渐向中间考虑
        while(searchRightIndex>searchLeftIndex){
            // step.1 在左侧寻找比中间值大或相等的值索引 (递增可能导致搜寻索引与中值索引相等) ->可能包含中值自身
            while(arr[searchLeftIndex]<middleVal){
                searchLeftIndex++;
            }
            // step.2 在右侧寻找比中间值小或相等的值索引 (递增可能导致搜寻索引与中值索引相等) ->可能包含中值自身
            while(arr[searchRightIndex]>middleVal){
                searchRightIndex--;
            }
            // step.3 如果两个搜寻索引相遇,则结束本次流程
            if(searchRightIndex<=searchLeftIndex){
                // 通常发生在一轮排序的最后
                break;
            }
            // step.4 如果没有相遇, 且各自能找到对应的待置换索引, 则两个索引相互交换
            // 注: 如果搜寻索引与中值索引相等, 则此步会将中值挪到原来的右侧搜寻索引上. 此种情况, 不妨称之为"中值替换"情况
            // 在出现"中值替换"情况下, 还可能出现另一种特殊的中值替换, 即"异位中值替换". 如果数组有相同元素, 且中值出现了不止一次, 则会出现这种"异位中值替换"的情况
            temp=arr[searchLeftIndex];
            arr[searchLeftIndex]=arr[searchRightIndex];
            arr[searchRightIndex]=temp;

            // 如果左侧待置换数量与右侧待置换数量不相等, 则使用中间值替代不足之处

            // 以下情况, 仅发生于"中值替换"情况下. 如果不出现"中值替换", 可无视
            // step.5 右侧(!因为值替换, 索引用左索引判定)搜寻索引提前遇到中间值, 右侧搜寻索引递进一步
            // 在不出现"异位中值替换"的情况下, 左右搜寻索引一旦到了中值地位, 便不会向内推进, 只会左右相互切换, 形成向内冒泡的情况
            // 在出现"异位中值替换"的情况下, 右侧搜寻索引会首先打破这种情况, 向内推进
            if(arr[searchLeftIndex]==middleVal){
                // 如果不执行这一步,
                searchRightIndex--;
            }
            // step.6 左侧(!因为值替换, 所以用右索引判定)搜索索引提前遇到中间值, 左侧搜寻索引递进一步
            if(arr[searchRightIndex]==middleVal){
                searchLeftIndex++;
            }
        }

        // 原左右索引回退, 以方便以后递归. 发生于左右索引相聚于中间值
        if (searchLeftIndex==searchRightIndex) {
            searchLeftIndex++;
            searchRightIndex--;
        }

        // 对中值的左侧部再次进行递归排序
        if(leftIndex<searchRightIndex){
           sort(arr,leftIndex,searchRightIndex);
        }
        // 对中值的右侧部再次进行递归排序
        if(searchLeftIndex<rightIndex){
            sort(arr,searchLeftIndex,rightIndex);
        }

    }
}
